#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class cmp
{
public:
	bool operator()(const ListNode* n1, const ListNode* n2)
	{
		return n1->val < n2->val;
	}
};
//ListNode* mergeKLists(vector<ListNode*>& lists)
//{
//	priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
//	for (int i = 0; i < lists.size(); i++)
//	{
//		while (lists[i])
//		{
//			heap.push(lists[i]);
//			lists[i] = lists[i]->next;
//		}
//	}
//	ListNode* head = new ListNode(0);
//	while (!heap.empty())
//	{
//		ListNode* top = heap.top();
//		heap.pop();
//		top->next = head->next;
//		head->next = top;
//	}
//	ListNode* ret = head->next;
//	delete head;
//	return ret;
//}
ListNode* _mergeKLists(vector<ListNode*>& lists,int left,int right) 
{
	if (left > right) return nullptr;
	if (left == right) return lists[left];
	int mid = left + (right - left) / 2;
	ListNode* l1 = _mergeKLists(lists, left, mid);
	ListNode* l2 = _mergeKLists(lists, mid+1, right);
	ListNode* head = new ListNode(0);
	ListNode* cur=head, *cur1 = l1, * cur2 = l2;
	while (cur1 && cur2)
	{
		if (cur1->val <= cur2->val)
		{
			cur->next = cur1;
			cur = cur->next;
			cur1 = cur1->next;
		}
		else
		{
			cur->next = cur2;
			cur = cur->next;
			cur2 = cur2->next;
		}
	}
	while (cur1)
	{
		cur->next = cur1;
		cur = cur->next;
		cur1 = cur1->next;
	}
	while (cur2)
	{
		cur->next = cur2;
		cur = cur->next;
		cur2 = cur2->next;
	}
	cur = head->next;
	delete head;
	return cur;
}
ListNode* mergeKLists(vector<ListNode*>& lists)
{
	return _mergeKLists(lists, 0, lists.size() - 1);
}
ListNode* reverseKGroup(ListNode* head, int k) 
{
	int count = 0;
	ListNode* cur = head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	int n = count / k;
	ListNode* newhead = new ListNode(0);
	cur = newhead;
	while (k--)
	{
		ListNode* tmp = cur;
		for (int i = 0; i < k; i++)
		{
			ListNode* next = cur->next;
			cur->next = tmp->next;
			tmp->next = cur;
			cur = next;
			next = next->next;
		}
	}
	head = newhead->next;
	delete newhead;
	return head;
}
vector<int> twoSum(vector<int>& nums, int target) 
{
	unordered_map<int,int> hash;
	for (int i = 0; i < nums.size(); i++)
	{
		if (hash.count(target - nums[i])) return { hash[target - nums[i]],i };
	}
	return vector<int>();
}
int main()
{
	
	return 0;
}
